//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 
//
// 
//
// 示例： 
//
// 输入：n = 3
//输出：[
//       "((()))", 
//       "(()())", 
//       "(())()", 
//       "()(())", 
//       "()()()"
//     ]
// 
// Related Topics 字符串 回溯算法 
// 👍 1248 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：括号生成
public class P22GenerateParentheses {

    /**
     * 思路: 看网上的答案。 递归回溯
     *
     * 执行用时： 1 ms , 在所有 Java 提交中击败了 96.78% 的用户 内存消耗： 39.9 MB , 在所有 Java 提交中击败了 50.13% 的用户
     *
     */

    //leetcode submit region begin(Prohibit modification and deletion)
    public class Solution {

        // 做加法
        public List<String> generateParenthesis(int n) {
            List<String> res = new ArrayList<>();
            // 特判
            if (n == 0) {
                return res;
            }
            dfs("", 0, 0, n, res);
            return res;
        }

        /**
         * 描述：
         *
         * @param str   字符串当前
         * @param left  已使用左括号数
         * @param right 已使用右括号数
         * @param n     总括号数
         * @param res   结果集合
         * @date: 2020/8/19 15:19
         */
        private void dfs(String str, int left, int right, int n, List<String> res) {
            if (left == n && right == n) {
                res.add(str);
            }
            if (left < right) {
                return;
            }

            if (left < n) {
                dfs(str + "(", left + 1, right, n, res);
            }
            if (right < n) {
                dfs(str + ")", left, right + 1, n, res);
            }

        }
    }

    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P22GenerateParentheses().new Solution();
        System.out.println(solution.generateParenthesis(0));
        System.out.println(solution.generateParenthesis(1));
        System.out.println(solution.generateParenthesis(2));
        System.out.println(solution.generateParenthesis(3));
        System.out.println(solution.generateParenthesis(4));

        // n=4: ["(((())))", "((()()))", "((())())", "((()))()", "(()(()))", "(()()())", "(()())()", "(())(())", "(())()()", "()((()))", "()(()())", "()(())()", "()()(())", "()()()()"]
    }

}